| 翻訳と辞書 |
| Heavy path decomposition ： ウィキペディア英語版 |
Heavy path decomposition
In combinatorial mathematics and theoretical computer science, heavy path decomposition (also called heavy-light decomposition) is a technique for decomposing a rooted tree into a set of paths. In a heavy path decomposition, each non-leaf node selects one "heavy edge", the edge to the child that has the greatest number of descendants (breaking ties arbitrarily). The selected edges form the paths of the decomposition.
==Decomposition into paths==
If the edges of a tree ''T'' are partitioned into a set of heavy edges and light edges, with one heavy edge from each non-leaf node to one of its children, then the subgraph formed by the heavy edges consists of a set of paths, with each non-leaf vertex belonging to exactly one path, the one containing its heavy edge. Leaf nodes of the tree that are not the endpoint of a heavy edge may be considered as forming paths of length zero. In this way, each vertex belongs to exactly one of the paths. Each path has a head vertex, its topmost vertex.
Alternatively, the paths of heavy edges may be extended by including one light edge, the one from the head of the path to its parent.〔 In this variation of the decomposition, some vertices belong to multiple paths, but every edge of ''T'' belongs to exactly one path.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Heavy path decomposition」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|